public class mergeSort {
    int[] ret;
    public int[] sortArray(int[] nums) {
        // 给临时数组的长度设置成所给数组长度, 这样一定不会越界
        ret = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }


    public void mergeSort(int[] nums, int left, int right) {
        if(left >= right) {
            return;
        }
        // 1.根据中间节点划分区域
        int mid = left + ((right - left) >> 1);
        // 所划分区域情况:
        //   左区间         右区间
        // [left, mid] [mid + 1, right]
        // 先去左区间排, 再去右区间排
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // 2.合并两个有序数组
        // 1.创建一个新数组
        int cur1 = left, cur2 = mid + 1;
        int i = 0; // 新数组下标
        while(cur1 <= mid && cur2 <= right) {
            ret[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
        }

        // 上面的while只能保证一个数组中的指针走到最后
        // 因此需要把另一个没有走到数组最后的指针走完
        while(cur1 <= mid) {
            ret[i++] = nums[cur1++];
        }

        while(cur2 <= right) {
            ret[i++] = nums[cur2++];
        }

        // 2.将排好序的新数组放回原数组中
        for(int j = 0; j < right - left + 1; j++) {
            nums[j + left] = ret[j];
        }
    }
}
